export   class Queue<T> implements IPriorityQueue<T> {
     private _heap!: T[];
    private priorityGetter!: PriorityGetter<T>;
    private heapgetter?:IHeapGetSet<T>;
    private _opt:IQueueOptions<T>;
    private get heap(): T[]
    {
        if(this.heapgetter)
        {
            return this.heapgetter.getHeap();
        }
        // throw new Error(`heap getter 未获取`);
        return this._heap
    }
    private set heap(arr:T[])
    {
        if(this.heapgetter)
        {
              this.heapgetter.setHeap(arr);
        }
        else
        {
            this._heap = arr;
        }
        
    }
    /**
     *
     * @param options
     * options.comparator: function used to compare elements;
     * options.initialElements: elements to be put in priority queue initially in O(n) time
     */
    constructor(options: IQueueOptions<T>) {
        this._opt = options;
     
        this.priorityGetter = options.comparator;
        this.heapgetter = options.heapgetter;
        if (options.heapgetter) this.buildHeap(options.heapgetter.getHeap());
        if (options.initialElements) this.buildHeap(options.initialElements);
    }
    clone(): Queue<T> {
        const clone = new Queue<T>({
            comparator: this.priorityGetter,
            initialElements: this.heap.slice()
        });
        return clone;
    }
    getAt(idx:number):T
    {
      return  this.heap[idx];
    }
    deleteAt(idx: number): T[] | undefined {
        if (idx >=  this.heap.length) {
            return undefined;
        }
        const t =   this.heap.splice(idx,1);
        return t;
    }
    delete(ele:T)
    {
        const idx = this.heap.indexOf(ele);
        if(idx>=0)
        {
            this.heap.splice(idx,1);
        }
    }
    /**
     *
     * @returns size of priority queue in O(1)
     */
    size() {
      return this.heap.length;
    }

    /**
     *
     * @returns is priority queue empty in O(1)
     */
    isEmpty() {
      return this.size() === 0;
    }

    /**
     *
     * @returns top of priority queue in O(1), if priority queue is empty returns undefined
     */
    peek(): T {
      return this.heap[0];
    }

    /**
     * clears priority queue in O(1)
     */
    clear(): void {
        //this.heap.splice(0,this.heap.length)
        this.heap = [];
    }

    /**
     * checks if value exists in priority queue in O(n)
     */
    has(value: T,cmp?:EqualCmp<T>) {
      if(cmp)
      {
        return !!this.heap.find((ele) => cmp(ele, value));
      }
      return !!this.heap.find((ele) => ele === value);
    }

    /**
     *
     * @returns all values of priority queue in O(n)
     */
    values() {
      return this.heap ;
    }

    private buildHeap(array: T[]) {
        // this.heap =  array;
    //   this.heap = JSON.parse(JSON.stringify(array)) as T[];
       this.heap = _.sortBy(array,e=>-this.priorityGetter(e));
    }

    /**
     *
     * @param value element to be added to heap, adds it in O(log n) operations, n is size of heap
     * @returns size of heap
     */
    push(value: T) {

        const index = this.heap.findIndex(e=>this.priorityGetter(e)<this.priorityGetter(value) );
        if(index>=0)
        {
            this.heap.splice(index,0,value);
        }
        else
        {
            this.heap.push(value);
        }
        return this.size();
    }

    /**
     *
     * @param values elements to be added to heap, adds it in O(k * log n) operations, n is size of heap, k is number of elements added
     * @returns size of heap
     */
    pushMany(values: T[]) {
      values.forEach((value) => {
        this.push(value);
      });
      return this.size();
    }

    /**
     *
     * @returns top of priority queue and removes it from priority queue in O(log n), if priority queue is empty returns undefined
     */
    pop<U extends T=T>():U|undefined
    {
        if (this.isEmpty()) {
            return undefined;
        }

        const returnValue = this.peek();
        this.heap.splice(0,1);
        
        return returnValue  as U;
    }

    top<U extends T=T>():U|undefined
    {
        if (this.isEmpty()) {
            return undefined;
            }
        return this.heap[0] as U;
    }
    dequeue()
    {
        return this.heap.splice(this.heap.length-1,1)[0]
    }
}
